Masala #0792

O'tkir xilma-xil konfet yeyishni juda yaxshi ko'radi. Ammo unga konfetlarni hammasini yeyishi mumkin emas. O'tkir ko'pi bilan necha xil konfet yeyishi mumkinligini topishga yordam bering! Bizga $N$ konfetdan iborat $arr[]$ massivi berilgan, bu yerda $N$ juft son va $arr[i]$ konfet turi. Muammo shundaki, agar ulardan faqat $N/2$ tasini yeyish mumkin bo'lsa, O'tkir yeyishi mumkin bo'lgan har xil turdagi konfetlarning maksimal sonini topishdir.

Birinchi qatorda $N$ butun juft son – massiv uzunligi beriladi $(1 ≤ N ≤ 2*10^5)$

Ikkinchi qatorda sizga $N$ ta son – massiv elementlari beriladi. Massiv elementlari 10¹⁸ dan oshmaydi.

Chiqish faylida yagona butun son O'tkir yeyishi mumkin bo'lgan har xil turdagi konfetlarning maksimal sonini chop eting.